def bubble_sort(data):
    n = len(data)
    for i in range(n):
        # 每次遍历将最大的元素移动到末尾
        for j in range(0, n - i - 1):
            # 如果当前元素大于下一个元素，则交换它们
            if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]
    return data


def quick_sort(data):
    # 如果数组长度小于等于1，直接返回数组（递归终止条件）
    if len(data) <= 1:
        return data

    # 选择基准值
    pivot = data[0]

    # 将数组分为小于基准值和大于基准值的两部分
    less_than_pivot = [x for x in data[1:] if x <= pivot]
    greater_than_pivot = [x for x in data[1:] if x > pivot]

    # 对小于基准值和大于基准值的部分分别递归调用快速排序
    return quick_sort(less_than_pivot) + [pivot] + quick_sort(greater_than_pivot)


def shell_sort(data):
    n = len(data)
    gap = n // 2

    while gap > 0:
        for i in range(gap, n):
            temp = data[i]
            j = i
            while j >= gap and data[j - gap] > temp:
                data[j] = data[j - gap]
                j -= gap
            data[j] = temp
        gap //= 2
    return data


def insertion_sort(data):
    for i in range(1, len(data)):
        key = data[i]
        j = i-1
        while j >=0 and key < data[j]:
            data[j+1] = data[j]
            j -= 1
        data[j+1] = key
    return data